package exercises.newcoder.solution;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <a href="https://www.nowcoder.com/practice/0383714a1bb749499050d2e0610418b1?tpId=40&&tqId=21333&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking">
 * KY2 成绩排序</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 牛客网早期描述不太好
 * <p>
 * 要求:
 * <ul>
 *     <li>稳定排序</li>
 * </ul>
 *
 * @author or2
 * @date 2021年10月01日 时间: 10:09
 */
public class Graduate2 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String amount;
        while ((amount = reader.readLine()) != null) {
            int totalNums = Integer.parseInt(amount);
            boolean isAscending = Integer.parseInt(reader.readLine()) == 1;
            Student[] students = new Student[totalNums];
            for (int i = 0; i < totalNums; i++) {
                String[] split = reader.readLine().split(" ");
                students[i] = new Student(split[0], Integer.parseInt(split[1]));
            }

//            Arrays.sort(students, (o1, o2) -> isAscending ? o1.grade - o2.grade : o2.grade - o1.grade);
            Comparator.setIsAscending(isAscending);
//            mergeSort(students, 0, students.length);
            quickSort(students, 0, students.length);
            /* 输出结果 */
            for (int i = 0, studentsLength = students.length; i < studentsLength; i++)
                System.out.println(students[i]);
        }
    }

    /**
     * 归并排序 - 稳定
     *
     * @param students 被排序的数组
     * @param start    排序开始下标
     * @param end      排序结束下标的后一个位置
     */
    private static void mergeSort(Student[] students, int start, int end) {
        /* 仅剩下一个元素时, 停止划分 */
        if (end - start < 2)
            return;
        /* 向下划分 */
        int mid = start + (end - start >> 1);
        mergeSort(students, start, mid);
        mergeSort(students, mid, end);
        /* 合并两个有序数组 */
        Student[] auxiliaryArr = new Student[end - start];
        int size = 0, left = start, right = mid;
        /* 根据大小依次放入辅助数组 */
        /* 注意判断条件, 是否稳定的关键 */
        while (true)
//            if (students[left].compareTo(students[right]) <= 0) {
            if (Comparator.compare(students[left], students[right]) <= 0) {
                auxiliaryArr[size++] = students[left++];
                /* 左数组结束 */
                if (left == mid) {
                    System.arraycopy(students, right, auxiliaryArr, size, end - start - size);
                    break;
                }
            } else {
                auxiliaryArr[size++] = students[right++];
                if (right == end) {
                    System.arraycopy(students, left, auxiliaryArr, size, end - start - size);
                    break;
                }
            }
        /* 将合并后的数组拷贝回原数组 */
        for (int i = 0, auxiliaryArrLength = auxiliaryArr.length; i < auxiliaryArrLength; i++)
            students[start + i] = auxiliaryArr[i];
    }

    public static void quickSort(Student[] students, int start, int end) {
        /* 防止退化 */
        Student beacon = students[(int) (Math.random() * (end - start)) + start];

        /* 三路快排 */
        int lt = start, eq = lt, gt = end;
        while (eq != gt) {
            int compare = Comparator.compare(students[eq], beacon);
            if (compare == 0)
                eq++;
            else if (compare < 0) {
                swap(students, lt++, eq++);
            } else
                swap(students, eq, --gt);
        }

        if (start < lt)
            quickSort(students, start, lt);
        if (gt < end)
            quickSort(students, gt, end);
    }

    /**
     * 进行元素交换
     *
     * @param students 元素所在数组
     * @param index1   元素一的下标
     * @param index2   元素一的下标
     */
    private static void swap(Student[] students, int index1, int index2) {
        Student temp = students[index1];
        students[index1] = students[index2];
        students[index2] = temp;
    }

    private static class Comparator {
        private static boolean isAscending;

        public static void setIsAscending(boolean isAscending) {
            Comparator.isAscending = isAscending;
        }

        public static int compare(Student s1, Student s2) {
            int compare = s1.compareTo(s2);
            return isAscending ? compare : -compare;
        }
    }

    private static class Student implements Comparable<Student> {
        private String name;
        private int grade;

        public Student(String name, int grade) {
            this.name = name;
            this.grade = grade;
        }

        @Override
        public int compareTo(Student o) {
            return Integer.compare(grade, o.grade);
        }

        @Override
        public String toString() {
            return String.format("%s %d", name, grade);
        }
    }
}
